package leetcode.d_1_99;

// https://leetcode.cn/problems/first-missing-positive/
// 缺失的第一个正数
public class P41 {
    public int firstMissingPositive(int[] nums) {
        // 对于一个长度为 N 的数组，其中没有出现的最小正整数只能在 [1,N+1] 中
        int n = nums.length;
        int[] array = new int[n+1];
        for (int i=0; i<n; i++) {
            if (nums[i] > 0 && nums[i] < n+1) {
                array[nums[i]]++;
            }
        }

        for(int i=1; i<=n; i++) {
            if (array[i] == 0) {
                return i;
            }
        }
        return n+1;
    }

    // 转成数组下标，然后遍历数组
    public int firstMissingPositive1(int[] nums) {
        int maxNum = 0; // 记录最大值
        for (int i=0; i<nums.length; i++) {
            if (nums[i] > maxNum) {
                maxNum = nums[i];
            }
            if (nums[i] < 0) {
                nums[i] = 0; // 负数转成0
            }
        }
        if (maxNum == 0) {
            return 1;
        }

        // array数组，如果array[i]==0则该正数不存在。
        int[] array = new int[maxNum+1];
        for (int i=0; i<nums.length; i++) {
            array[nums[i]]++;
        }
        for (int i=1; i<=maxNum; i++) {
            if (array[i] == 0) {
                return i;
            }
        }
        return maxNum+1;
    }

    public static void main(String[] args) {
        P41 test = new P41();
        System.out.println(test.firstMissingPositive(new int[]{1,2,0})); // 3
        System.out.println(test.firstMissingPositive1(new int[]{1,2,0})); // 3
    }
}
